#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<math.h>
typedef struct ListNode
{
	int val;
	struct ListNode* next;
}ListNode;
//ListNode* detectcircle(ListNode* head)
//{
//	assert(head);
//	ListNode* slow = head, * fast = head;
//	while (fast && fast->next)
//	{
//		slow = slow->next;
//		fast = fast->next->next;
//		if (slow == fast)
//		{
//			ListNode* meet = slow;
//			while (meet != head)
//			{
//				head = head->next;
//				meet = meet->next;
//			}
//			return meet;
//		}
//	}
//}
ListNode* getintersectionnode(ListNode* head1, ListNode* head2)
{
	int len1 = 0, len2 = 0;
	while (head1)
	{
		head1 = head1->next;
		len1++;
	}
	while (head2)
	{
		head2 = head2->next;
		len2++;
	}
	if (head1 != head2)
	{
		return NULL;
	}
	int  n = abs(len1 - len2);
	ListNode* longlist = head1;
	ListNode* shortlist = head2;
	if (len1 < len2)
	{
		longlist = head2;
		shortlist = head1;
	}
	while (n--)
	{
		longlist = longlist->next;
	}
	while (longlist != shortlist)
	{
		longlist = longlist->next;
		shortlist = shortlist->next;
	}
	return shortlist;

	

}
ListNode* detectcircle(ListNode* head)
{
	assert(head);
	ListNode* slow = head, * fast = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
		if (slow == fast)
		{
			ListNode* meet = slow;
			ListNode* newhead = meet->next;
			meet->next = NULL;
			 return getintersectionnode(newhead,head);
		}
	}
	return NULL;
}

int main()
{


}